package cn.z2huo.algorithm.sort.mergeSort;

public class MergeSort {
	
	public void mergeSort(int[] array, int[] array2) {
		int len = 1;
		int n = array.length;
		while(len<array.length) {
			mergePass(array, array2, len, n);
			len += len;
			mergePass(array2, array, len, n);
			len += len;
		}
	}
	
	public void mergePass(int[] array, int[] array2, int len, int n) {
		int i=0;
		while(i<=n-2*len) {
			merge(array, array2, i, i+len-1, i+2*len-1);
			i = i+2*len;
		}
		if(i+len<n) {
			merge(array, array2, i, i+len-1, n-1);
		}else {
			for(int j=i; j<=n-1; j++) {
				array2[j] = array[j];
			}
		}
	}
	
	public void merge(int[] array, int[] array2, int l, int m, int r) {
		int i = l, j = m+1, k = r;
		while((i<=m)&&(j<=r)) {
			if(array[i]<=array[j]) {
				array2[k++] = array[i++];
			}else {
				array2[k++] = array[j++];
			}
		}
		if(i>m) {
			for(int q=j; q<=r; q++) {
				array2[k++] = array[q];
			}
		}else {
			for(int q=i; q<=m; q++) {
				array2[k++] = array[q];
			}
		}
	}
	
	public void printArray(int[] array) {
		for(int i=0; i<array.length; i++) {
			System.out.print(array[i] + " ");
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		int[] array = {11,13,2,34,55,9,44,122,32,2,9};
		int[] array2 = new int[array.length];
		MergeSort ms = new MergeSort();
		ms.mergeSort(array, array2);
		ms.printArray(array2);
	}
}
